import java.util.ArrayList;
import java.util.Collection;


/**
 * This class backs up the data structure that helps perform Kruskal algorithm.
 * @author Hyangjin Lee
 *
 */
public class UnionFind {

	private int[] ID;
	private Object[] edges;
	
	/**
	 * Constructs UnionFind
	 * @param edgeList the list of edges
	 */
	public UnionFind(EdgeList edgeList) {
		Collection<Edge> edgelist = edgeList.getEdges();
		edges = edgelist.toArray();
		ID = new int[edges.length];
		for(int i=0; i<ID.length; i++)
		{
			ID[i] = i;
			
			for(int j=i+1; j<edges.length; j++)
			{
				if(((Edge)edges[i]).getU()==((Edge)edges[j]).getU() 
						|| ((Edge)edges[i]).getU()==((Edge)edges[j]).getV())
				{
					ID[j] = ID[i];
				}
				if(((Edge)edges[i]).getV()==((Edge)edges[j]).getU() 
						|| ((Edge)edges[i]).getV()==((Edge)edges[j]).getV())
				{
					ID[j] = ID[i];
				}
			}
		}
	}

	/**
	 * Assume that u and v are vertices that were in the edgeList. Determine if they are currently
	 * in the same component of this UnionFind structure
	 * 
	 * @param u
	 *            a vertex
	 * @param v
	 *            a vertex
	 * @return true if u and v are in the same component, false otherwise
	 */
	public boolean sameComponent(Vertex u, Vertex v) {
		boolean same = false;
		for(int i=0; i<edges.length; i++)
		{
			int a=0, b=0;
			for(int j=i+1; j<edges.length; j++)
			{
				if(((Edge)edges[i]).getU().equals(u) || ((Edge)edges[i]).getV().equals(u))
				{
					a=ID[i];
					if(((Edge)edges[j]).getU().equals(v) || ((Edge)edges[j]).getV().equals(v))
					{
						b=ID[j];
						if(a==b)
						{
							same = true;
						}
					}
				}

			}
		}
		return same;
	}

	/**
	 * Assume that u and v are vertices that were in the edgeList. Assume that u and v are in
	 * different components. Union the component containing u and the component containing v
	 * together.
	 * 
	 * @param u
	 *            a vertex
	 * @param v
	 *            a vertex
	 */
	public void union(Vertex u, Vertex v) {
		// TODO
	}
}
